from sys import stdin,stdout
from math import gcd,sqrt,factorial,pi,inf
from collections import deque,defaultdict
from bisect import bisect,bisect_left
from time import time
from itertools import permutations as per
input=stdin.readline
R=lambda:map(int,input().split())
I=lambda:int(input())
S=lambda:input().rstrip('\r\n')
L=lambda:list(R())
P=lambda x:stdout.write(str(x)+'\n')
lcm=lambda x,y:(x*y)//gcd(x,y)
nCr=lambda x,y:(f[x]*inv((f[y]*f[x-y])%N))%N
inv=lambda x:pow(x,N-2,N)
sm=lambda x:(x**2+x)//2
N=10**9+7
def dsu(x):
p=x
while v[x]!=x:
x=v[x]
v[p]=x
return x
for _ in range(I()):
n,m,k=R()
x = 0
g=sorted([L() for i in range(m)],key=lambda x:x[-1])
v=[i for i in range(n+1)]
d=inf
ans=0
for a,b,s in g:
p=dsu(a)
q=dsu(b)
d=min(d,abs(s-k))
if p!=q:
v[p]=v[q]
ans+=max(0,s-k)
print(ans if ans else d)#pragma GCC optimize("03")
#include<bits/stdc++.h>
using namespace std;
#define T int t; cin>>t; while(t--)
#define ll long long
#define vec vector
#define all(x) x.begin(), x.end()
const double pi=3.14159265358979323846;
const int N=2e5+5, mod=1e9+7, inf=0x3f3f3f3f;
int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
class dsu{
int parent[N], sz[N];
public:
dsu(int n){
for(int i=1; i<=n; i++) parent[i]=i, sz[i]=1;
}
int find_parent(int u){
if(parent[u]==u) return u;
return parent[u]= find_parent(parent[u]);
}
bool is_con(int u, int v){
return find_parent(u)== find_parent(v);
}
void con(int u, int v){
u= find_parent(u), v= find_parent(v);
if(is_con(u,v)) return;
if(sz[u]<sz[v]) swap(u, v);
parent[v]=u;
sz[u]+=sz[v];
}
};
int main(){
ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
T{
ll n, m, k; cin>>n>>m>>k;
dsu H(n);
ll sum=0, res=mod;
vec<pair<ll, pair<int, int>>>x;
for(int i=0; i<m; ++i){
int a, b, c; cin>>a>>b>>c;
res=min(res, abs(c-k));
x.push_back({max((ll)0, c-k),{a, b}});
}
sort(all(x));
for(auto it: x){
int a=it.second.first, b=it.second.second, c=it.first;
if(!c) H.con(a, b);
else{
if(!H.is_con(a, b)){
sum+=c;
H.con(a, b);
}
}
}
if(!sum)cout<<res<<'\n';
else cout<<sum<<'\n';
};
}734A - Anton and Danik | 1300B - Assigning to Classes |
1647A - Madoka and Math Dad | 710A - King Moves |
1131A - Sea Battle | 118A - String Task |
236A - Boy or Girl | 271A - Beautiful Year |
520B - Two Buttons | 231A - Team |
479C - Exams | 1030A - In Search of an Easy Problem |
158A - Next Round | 71A - Way Too Long Words |
160A - Twins | 1A - Theatre Square |
1614B - Divan and a New Project | 791A - Bear and Big Brother |
1452A - Robot Program | 344A - Magnets |
96A - Football | 702B - Powers of Two |
1036A - Function Height | 443A - Anton and Letters |
1478B - Nezzar and Lucky Number | 228A - Is your horseshoe on the other hoof |
122A - Lucky Division | 1611C - Polycarp Recovers the Permutation |
432A - Choosing Teams | 758A - Holiday Of Equality |